// Author: combacsa@kaist.ac.kr
// http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1077

//#define COMPILE
#ifdef COMPILE

#include <fstream>

using namespace std;

int n, w;
int weight[1000], value[1000];
int d[10001];

void input() {
    ifstream in("input.txt");
    
    in >> n >> w;
    for (int i = 0; i < n; i++)
        in >> weight[i] >> value[i];
    
    in.close();
}

void solve() {
    d[0] = 0;
    for (int i = 1; i <= w; i++) {
        d[i] = d[i-1];
        for (int j = 0; j < n; j++) {
            if (i - weight[j] >= 0) {
                if (d[i] < d[i - weight[j]] + value[j]) {
                    d[i] = d[i - weight[j]] + value[j];
                }
            }
        }
    }
}

void output() {
    ofstream out("output.txt");
    out << d[w];
    out.close();
}

int main() {
    input();
    solve();
    output();
    return 0;
}


#endif
